/******************************************************************************

    Copyright (C) 2019 ErisedMedia
    All Rights Reserved.

    This source code and any compilation or derivative thereof is the
    proprietary information of ErisedMedia and is
    confidential in nature.
    Under no circumstances is this software to be exposed to or placed under an
    Open Source License of any type without the expressed written permission of
    ErisedMedia.

******************************************************************************/

/******************************************************************************

    File:   Polygon.cc
    Brief:  Polygon实现.

******************************************************************************/

/******************************************************************************

    Rev     Date        Author      Comments
--------------------------------------------------------------------------------
    001     20191206    RunyuanYe        Original

--------------------------------------------------------------------------------
    For consistency and standardisation retain the Section Separators.

*******************************************************************************/

/******************************************************************************
*
*   INCLUDE FILES
*
******************************************************************************/

#include "Polygon.h"

/******************************************************************************
*
*    LOCAL MACROS
*
******************************************************************************/


/******************************************************************************
*
*    LOCAL TYPEDEFS
*
******************************************************************************/


/******************************************************************************
*
*    STATIC DATA
*
******************************************************************************/


/******************************************************************************
*
*    EXPORTED DATA
*
******************************************************************************/


/******************************************************************************
*
*    EXPORTED FUNCTION
*
******************************************************************************/


/******************************************************************************
*
*    STATIC FUNCTION PROTOTYPES
*
******************************************************************************/


/******************************************************************************
*
*    FUNCTION IMPLEMENTATION
*
******************************************************************************/

//精度误差比较
static inline int dcmp(float x)
{
    static const float eps = 1e-8;
    if(x > eps) return 1;
    return x < -eps ? -1 : 0;
}

static inline float cross(Point_S a,Point_S b,Point_S c)
{//叉积
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}

static inline Point_S intersection(Point_S a,Point_S b,Point_S c,Point_S d)
{//传入四点即两直线，输出交点
    Point_S p = a;
    float t =((a.x-c.x)*(c.y-d.y)-(a.y-c.y)*(c.x-d.x))/((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x));
    p.x +=(b.x-a.x)*t;
    p.y +=(b.y-a.y)*t;
    return p;//输出交点，证明用数学方法易证
}

// static inline float _PolygonArea(Point_S p[], int n)
// {//计算多边形面积，三角剖分
//     if(n < 3) return 0.0;
//     float s = p[0].y * (p[n - 1].x - p[1].x);
//     p[n] = p[0];
//     for(int i = 1; i < n; ++ i)
//         s += p[i].y * (p[i - 1].x - p[i + 1].x);
//     return fabs(s * 0.5);//叉乘出来是平行四边形面积故/2，且顺逆方向不定，故取ABS变正
// }

static inline float _PolygonArea(const Point_S p[], int n)
{//计算多边形面积，三角剖分
    if(n < 3) return 0.0f;
    float s = p[0].y * (p[n - 1].x - p[1].x);
    // p[n] = p[0];
    int i;
    int c = n - 1;
    for(i = 1; i < c; ++i)
        s += p[i].y * (p[i - 1].x - p[i + 1].x);
    s += p[i].y * (p[i - 1].x - p[0].x);
    return fabs(s * 0.5f);//叉乘出来是平行四边形面积故/2，且顺逆方向不定，故取ABS变正
}

static inline float CPIA(Point_S a[], Point_S b[], int na, int nb)
{//传入两个三角形，求相交部分的凸包
    Point_S p[20], tmp[20];           //复制点集与临时点集（P其实可以用B来做
    int tn, sflag, eflag;           //每轮相交凸包的点，叉乘符号
    a[na] = a[0], b[nb] = b[0];     //末点用初点复制方便首末点连边
    memcpy(p,b,sizeof(Point_S)*(nb + 1));         //把B复制到P
    for(int i=0;i<na&&nb>2;i++){                //扫一次A
        sflag=dcmp(cross(a[i+1],p[0],a[i]));    //取A两点与B第一点求叉乘符号
        for(int j=tn=0;j<nb;j++,sflag=eflag){   //扫一次B，更新TMP，TN是点数
            if(sflag>=0)tmp[tn++]=p[j];         //叉乘为正就是B数组的那个点压入
            eflag=dcmp(cross(a[i+1],p[j+1],a[i]));//求叉乘符号
            if((sflag^eflag)==-2)               //1异或-1等于-2
            tmp[tn++]=intersection(a[i],a[i+1],p[j],p[j+1]);//求交点
        }
        memcpy(p, tmp, sizeof(Point_S) * tn);     //把TMP复制到P
        nb = tn, p[nb] = p[0];//TN即TMP点数记到NB
    }//其实该是NP表示P数组个数，这里省了个变量就用NB表示，下面第二行做参数而已
    if(nb < 3) return 0.0f;      //相交部分凸包不够三个点，面积就是0
    return _PolygonArea(p, nb);  //求出相交凸包部分的面积
}

// 求两多边形相交的面积，a和b分别的空间要比na和nb多1个
float _PolygonIA(Point_S a[], Point_S b[], int na, int nb)
{//传入两个多边形的点
    int i,j;                            //循环变量
    Point_S t1[4],t2[4];                  //其实T13与T23没用上
    float res=0,num1,num2;             //答案初始化，及叉乘符号
    a[na]=t1[0]=a[0],b[nb]=t2[0]=b[0];  //初始化T1,T2和ANA,BNB
    for(i=2;i<na;i++){                  //扫一次第一个多边形全部点
        t1[1]=a[i-1],t1[2]=a[i];        //每次在第一个多边形取两个点赋给T11,T12
        num1=dcmp(cross(t1[1],t1[2],t1[0]));//求出叉乘符号
        if(num1<0)swap(t1[1],t1[2]);    //小于0则改变T11,T12可使叉乘符号变正，实即改变T1三个点的顺逆
        for(j=2;j<nb;j++){              //扫一次第二个多边形全部点
            t2[1]=b[j-1],t2[2]=b[j];    //然后再在第二个多边形取两个点赋给T21,T22
            num2=dcmp(cross(t2[1],t2[2],t2[0]));//求出叉乘符号
            if(num2<0)swap(t2[1],t2[2]);//小于0则改变T11,T12可使叉乘符号变正，实即改变T1三个点的顺逆
            res+=CPIA(t1,t2,3,3);       //累加相交部分面积
        }
    }
    return res;
}


// 计算多变形面积, 顶点要求逆时针
float PolygonArea(const std::vector<Point_S> polygon)
{
    return _PolygonArea(polygon.data(), polygon.size());
}

// 求两多边形相交的面积, 顶点要求逆时针
float PolygonIA(std::vector<Point_S> polygon1, std::vector<Point_S> polygon2)
{
    float ia = 0.0f;
    int n1 = polygon1.size();
    int n2 = polygon2.size();
    Point_S* p1 = new Point_S[n1+4];
    Point_S* p2 = new Point_S[n2+4];
    if((!p1) || (!p2))
    {
        goto _EXIT;
    }

    memcpy(p1, polygon1.data(), sizeof(Point_S)*n1);
    memcpy(p2, polygon2.data(), sizeof(Point_S)*n2);

    ia = _PolygonIA(p1, p2, polygon1.size(), polygon2.size());

_EXIT:
    if(p1) delete[] p1;
    if(p2) delete[] p2;
    return ia;
}
